package com.zk.algorithm.array;

import com.zk.algorithm.annotation.BianChengZhiMei;
import com.zk.algorithm.bean.Interval;

import java.util.Arrays;
import java.util.List;

/**
 * 区间重合判断，对比 {@link MergeIntervals}
 * 给定一个源区间，和 N 个无序的目标区间，判断源区间是否在目标区间内
 *
 * @author zk
 */
@BianChengZhiMei("2.19")
public class OverlappingRange {

    public static void main(String...args) {
        OverlappingRange overlappingRange = new OverlappingRange();

        System.out.println(overlappingRange.isInRange(new Interval(1, 6), Arrays.asList(
                new Interval(2, 3),
                new Interval(1, 2),
                new Interval(3, 9)
        )));

        System.out.println(overlappingRange.isInRange(new Interval(3, 9), Arrays.asList(
                new Interval(1, 3),
                new Interval(2, 6),
                new Interval(8, 10),
                new Interval(15, 18)
        )));
    }

    // [x,y] 是否在几个无序区间内
    //
    // [1,6]
    // [2,3], [1,2], [3,9]
    public boolean isInRange(Interval src, List<Interval> targetList) {
        List<Interval> mergedTargetList = new MergeIntervals().merge(targetList);

        int start = 0;
        int end = mergedTargetList.size() - 1;

        // 二分搜索
        while (start <= end) {
            int mid = start + (end - start) / 2;
            Interval midInterval = mergedTargetList.get(mid);

            // (1) src 位于 mid 的左边
            //                 [______]
            //                 ↑
            //         midInterval.start
            //     [_____]
            //           ↑
            //       src.end
            if (src.end < midInterval.start) {
                end = mid - 1;
            } else if (src.start > midInterval.end) {
                // (2) src 位于 mid 的右边
                //
                //    [______]
                //           ↑
                //       midInterval.end
                //                  [_____]
                //                  ↑
                //               src.start
                start = mid + 1;
            } else {
                return src.start >= midInterval.start && src.end <= midInterval.end;
            }

        }

        return false;
    }

}
